package 高频题;

import java.util.Arrays;

public class 下一个排列_31 {
    public static void main(String[] args) {
        new 下一个排列_31().nextPermutation(new int[]{1, 3, 5, 4, 1});
    }

    public void nextPermutation(int[] nums) {
        int n = nums.length;
        int k = n - 1;
//        从后往前找，找到第一个下降的位置
        while (k > 0 && nums[k - 1] >= nums[k]) {
            k--;
        }
        //注意：这里跳出来，k还要往前移动一位才是我们要的那个值，比如数组[1,3,5,4,1]，到这里k=5

//        没找到降序位置：说明该序列已经是字典序最大的排列
        if (k == 0) {
            reverse(nums, 0, n - 1);
        } else {
            int u = k;
//            从 k 往后找，找到最小的比 k 要大的数
            //k - 1才是我们要的那个“[1,3,5,4,1]” k-1=3
            while (u < n - 1 && nums[u + 1] > nums[k - 1]) {
                u++;
            }
            //要交换的是k-1哦
            swap(nums, k - 1, u);
            reverse(nums, k, n - 1);
        }
    }

    /**
     * 反转 a到b的数组
     *
     * @param nums
     * @param a
     * @param b
     */
    void reverse(int[] nums, int a, int b) {
        int l = a, r = b;
        while (l < r) {
            swap(nums, l++, r--);
        }
    }

    /**
     * 原地交换俩元素
     *
     * @param nums
     * @param a
     * @param b
     */
    void swap(int[] nums, int a, int b) {
        int c = nums[a];
        nums[a] = nums[b];
        nums[b] = c;
    }
}
